﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
// 平衡 二叉搜索树。左边的树都比根小，右边的都比根大
//给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
//平衡 二叉搜索树的中序遍历就是升序的
class Sol108
{
    public TreeNode SortedArrayToBST(int[] nums)
    {
        int len=nums.Length;


      return  ArrayToBST(nums, 0, len-1);

    }

    public TreeNode ArrayToBST(int[] nums, int left,int right)
    {

        Console.WriteLine("left:  " +left+ "  right:  " +right);
        if (right < left)
        {
            return null;
        }
        int mid = (right+left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = ArrayToBST( nums,left , mid-1);
        root.right = ArrayToBST( nums,mid+1, right); 
        return root;

    }

}
class Program108
{
    static void Main108(string[] args)
    {
        int[] inOrder = { -10, -3, 0, 5, 9 };
        Sol108 sol= new Sol108();
         TreeNode root= sol.SortedArrayToBST(inOrder);

        //层序输出一下
        Solution105 solution105 = new Solution105();
        solution105.levelOrder(root);

    }
}